/**
 * Copyright (c) 2008, Daniel Gee. All Rights reserved.
 * See LICENSE.txt for more details.
 */
package com.rl.dungeon.fov;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import com.rl.dungeon.Location;

/**
 * Performs precise permissive field of view calculations using on Jonathon Duerig's algorithm
 * presented at Roguebasin's <a href=
 * "http://roguebasin.roguelikedevelopment.org/index.php?title=Precise_Permissive_Field_of_View">
 * Precise Permissive Field of View</a> page.
 * <p>
 * Credit also goes to Aaron MacDonald, who ported the C++ version of the library into python, which
 * I can read and understand much much better than I can understand C++.
 * </p>
 * 
 * @author Daniel Gee
 */
public class PrecisePermissiveFOV
{
	/**
	 * Used by LOS when it calls "visitCoord()" but doesn't want to affect anything.
	 */
	private static final VisitEffect Do_Nothing_Visit = (loc) ->
	{
	};

	/**
	 * Performs FOV calculations to determine if a given square is visible from another square. For
	 * each visible square, the VisitEffect is applied to that square exactly once. The VisitEffect
	 * shouldn't modify a square's vision blocking, or FOV won't be computed properly. Diagonals are
	 * counted 1:1 with regards to the radius, so the resulting area checked is actually a square.
	 * 
	 * @param start
	 *            the starting point of the FOV computation.
	 * @param mapEdge
	 *            the location of the maximum x and y values possible on this map.
	 * @param radius
	 *            the maximum radius of the view field
	 * @param effect
	 *            the effect to apply to each viewed square
	 * @param check
	 *            the check to see if a square blocks vision or not.
	 */
	public static void computeFOV(Location start, Location mapEdge, int radius, VisitEffect effect,
			VisionCheck check)
	{
		/**
		 * Track all locations visited.
		 */
		Set<Location> visited = new HashSet<>();

		/**
		 * Always visit the center position.
		 */
		effect.performEffect(start);
		visited.add(start);

		/**
		 * Decide on the limits of the searching out from the starting position.
		 */
		final int minX = Math.min(start.x, radius);
		final int maxX = Math.min(mapEdge.x - start.x - 1, radius);
		final int minY = Math.min(start.y, radius);
		final int maxY = Math.min(mapEdge.y - start.y - 1, radius);

		/**
		 * Quadrent 1
		 */
		PrecisePermissiveFOV.checkQuadrant(visited, start, 1, 1, maxX, maxY, effect, check);

		/**
		 * Quadrent 2
		 */
		PrecisePermissiveFOV.checkQuadrant(visited, start, 1, -1, maxX, minY, effect, check);

		/**
		 * Quadrent 3
		 */
		PrecisePermissiveFOV.checkQuadrant(visited, start, -1, -1, minX, minY, effect, check);

		/**
		 * Quadrent 4
		 */
		PrecisePermissiveFOV.checkQuadrant(visited, start, -1, 1, minX, maxY, effect, check);
	}

	/**
	 * Checks to see if Line of Sight exists between the two locations given. The method assumes
	 * that both locations are within the area that the {@link VisionCheck} can cover, and that both
	 * locations are already within whatever vision radius may be in use.
	 * 
	 * @param start
	 *            start point.
	 * @param end
	 *            end point.
	 * @param check
	 *            the check that determines if a square blocks vision or not.
	 * 
	 * @return If there is a line of sight between the two squares given.
	 */
	public static boolean hasLOS(Location start, Location end, VisionCheck check)
	{
		/**
		 * This tracks where we went. If our destination ends up in here, we win.
		 */
		Set<Location> visited = new HashSet<>();

		// Always visit the center.
		visited.add(start);

		// decide deltas and extents
		final int dx, dy;
		final int extentX, extentY;
		if (start.x <= end.x)
		{
			dx = 1;
			extentX = Math.max(end.x - start.x, 1);
		}
		else
		{
			dx = -1;
			extentX = Math.max(start.x - end.x, 1);
		}

		if (start.y <= end.y)
		{
			dy = 1;
			extentY = Math.max(end.y - start.y, 1);
		}
		else
		{
			dy = -1;
			extentY = Math.max(start.y - end.y, 1);
		}

		// Quadrant Check
		PrecisePermissiveFOV.checkQuadrant(visited, start, dx, dy, extentX, extentY,
				PrecisePermissiveFOV.Do_Nothing_Visit, check);

		return visited.contains(end);

	}

	/**
	 * Inserts a new "shallow" bump into the view specified at the location specified.
	 * 
	 * @param view
	 *            the view to add the bump to.
	 * @param loc
	 *            position of the new ViewBump.
	 */
	private static void addShallowBump(View view, Location loc)
	{
		view.shallowLine.xfinal = loc.x;
		view.shallowLine.yfinal = loc.y;

		view.shallowBump = new ViewBump(loc, view.shallowBump);

		ViewBump curBump = view.steepBump;
		while (curBump != null)
		{
			if (view.shallowLine.isAbove(curBump.location))
			{
				view.shallowLine.xinitial = curBump.location.x;
				view.shallowLine.yinitial = curBump.location.y;
			}
			curBump = curBump.parent;
		}
	}

	/**
	 * Inserts a new "steep" bump into the view specified at the x,y specified.
	 * 
	 * @param view
	 *            the view to add the bump to.
	 * @param loc
	 *            position of the new ViewBump.
	 */
	private static void addSteepBump(View view, Location loc)
	{
		view.steepLine.xfinal = loc.x;
		view.steepLine.yfinal = loc.y;

		view.steepBump = new ViewBump(loc, view.steepBump);

		ViewBump curBump = view.shallowBump;
		while (curBump != null)
		{
			if (view.steepLine.isBelow(curBump.location))
			{
				view.steepLine.xinitial = curBump.location.x;
				view.steepLine.yinitial = curBump.location.y;
			}
			curBump = curBump.parent;
		}
	}

	/**
	 * Examines a single quadrant of the field of view, expanding away from the center of the field
	 * along a series of diagonals that are perpendicular to the direction of expansion.
	 * 
	 * @param visited
	 *            a set of points already visited. A quadrant check adds to this.
	 * @param start
	 *            the starting point of the quadrant check.
	 * @param dx
	 *            the change applied to x when x changes.
	 * @param dy
	 *            the change applied to y when y changes.
	 * @param extentX
	 *            the upper or lower bound of x movement (delta from startX).
	 * @param extentY
	 *            the upper or lower bound of y movement (delta from startY).
	 * @param effect
	 *            the effect to apply to squares that are calculated to be visible.
	 * @param check
	 *            the metric used to determine if a square blocks sight for this check or not.
	 */
	private static void checkQuadrant(Set<Location> visited, Location start, int dx, int dy,
			int extentX, int extentY, VisitEffect effect, VisionCheck check)
	{
		/**
		 * Track all views within this quadrant.
		 */
		List<View> activeViews = new ArrayList<>();

		/**
		 * The starting view is the widest of all possible views.
		 */
		SightLine shallowLine = new SightLine(0, 1, extentX, 0);
		SightLine steepLine = new SightLine(1, 0, 0, extentY);
		activeViews.add(new View(shallowLine, steepLine));

		/**
		 * We scan "outwards" from the starting point, along a series of diagonals that are all of
		 * slope -1. maxIndex is a control value of sorts, that lets us resolve each point along
		 * these diagonals.
		 */
		int maxIndex = extentX + extentY + 1;
		int i, j;
		for (i = 1; i < maxIndex; i++)
		{
			int startJ = Math.max(i - extentX, 0);
			int maxJ = Math.min(i, extentY) + 1;
			for (j = startJ; j < maxJ; j++)
			{
				PrecisePermissiveFOV.visitCoord(visited, start, i - j, j, dx, dy, activeViews,
						effect, check);
				if (activeViews.isEmpty())
				{
					return;
				}
			}
		}
	}

	/**
	 * Removes the view at <code>viewIndex</code> from <code>activeViews</code> if both of the
	 * view's lines are colinear and they also pass through either extremity; (0,1) and (1,0). The
	 * corners of the source square cannot be used as the origin of a view, and so if this happens
	 * the view needs to be removed. This needs to be called after every view update for all views.
	 * 
	 * @param activeViews
	 *            the List of views to operate on.
	 * @param viewIndex
	 *            the view to inspect
	 * @return if the view inspected managed to stay in the list or not.
	 */
	private static boolean checkView(List<View> activeViews, int viewIndex)
	{
		SightLine shallowLine = activeViews.get(viewIndex).shallowLine;
		SightLine steepLine = activeViews.get(viewIndex).steepLine;

		if (shallowLine.isLineCollinear(steepLine)
				&& (shallowLine.isCollinear(0, 1) || shallowLine.isCollinear(1, 0)))
		{
			activeViews.remove(viewIndex);
			return false;
		}
		else
		{
			return true;
		}
	}

	/**
	 * Visits a single coordinate, and then modifies the appropriate view if the coordinate is a
	 * blocking one.
	 * 
	 * @param visited
	 *            the set of positions visited so far.
	 * @param start
	 *            the point that we started this FOV pass with.
	 * @param x
	 *            the relative x position from the start that we're visiting right now.
	 * @param y
	 *            the relative y position from the start that we're visiting right now.
	 * @param dx
	 *            the x delta, based on the current quadrant.
	 * @param dy
	 *            the y delta, based on the current quadrant.
	 * @param activeViews
	 *            the list of views to find the current view in.
	 * @param effect
	 *            the effect to apply to 'seen' squares.
	 * @param check
	 *            the check to determine if a square blocks.
	 */
	private static void visitCoord(Set<Location> visited, Location start, int x, int y, int dx,
			int dy, List<View> activeViews, VisitEffect effect, VisionCheck check)
	{
		/**
		 * Corners of the current coordinate. The x,y passed is the bottom left, but that's not
		 * sufficient for vision checks.
		 */
		Location topLeft = Location.of(x, y + 1);
		Location bottomRight = Location.of(x + 1, y);

		int viewIndex = 0;

		while (viewIndex < activeViews.size()
				&& activeViews.get(viewIndex).steepLine.isBelowOrCollinear(bottomRight))
		{
			/**
			 * The current square is above the current view's upper line and so it is ignored for
			 * this view. Other views may need it though, we look for one that can use it.
			 */
			viewIndex++;
		}

		if (viewIndex == activeViews.size()
				|| activeViews.get(viewIndex).shallowLine.isAboveOrCollinear(topLeft))
		{
			/**
			 * If viewIndex == activeViews.size(), then the square is above all views, and we can
			 * stop working on it.
			 */
			/**
			 * The active view's steep line is above this square, so if the activeView's shallow
			 * line is also above this square, then we can skip over it, since the active view is
			 * entirely above this square.
			 */
			return;
		}

		/**
		 * It is now known that the current square is within the active view. So we compute the
		 * "real" coordinates of the square on the map and visit it.
		 */
		int realX = x * dx;
		int realY = y * dy;

		/**
		 * It's possible for squares orthogonal to the center of the FOV to be within two view
		 * Quadrants at once, so we check one last time to make sure we haven't been here.
		 */
		Location currentLocation = start.translate(realX, realY);
		if (!visited.contains(currentLocation))
		{
			visited.add(currentLocation);
			effect.performEffect(currentLocation);
		}

		/**
		 * Now, if the square is empty, we can move on.
		 */
		if (!check.visionBlocked(currentLocation))
		{
			return;
		}

		/**
		 * For squares that block, we figure out exactly how it blocks, and adjust accordingly.
		 */

		/**
		 * The current square blocks both lines of the current view, so it completely ruins this
		 * view.
		 */
		if (activeViews.get(viewIndex).shallowLine.isAbove(bottomRight)
				&& activeViews.get(viewIndex).steepLine.isBelow(topLeft))
		{
			activeViews.remove(viewIndex);
		}
		/**
		 * The current square blocks just the shallow line of the current view, so it becomes a
		 * shallow bump for this view and the view is adjusted accordingly.
		 */
		else if (activeViews.get(viewIndex).shallowLine.isAbove(bottomRight))
		{
			PrecisePermissiveFOV.addShallowBump(activeViews.get(viewIndex), topLeft);
			PrecisePermissiveFOV.checkView(activeViews, viewIndex);
		}
		/**
		 * The current square blocks just the steep line of the current view, so it becomes a steep
		 * bump for this view and the view is adjusted accordingly.
		 */
		else if (activeViews.get(viewIndex).steepLine.isBelow(topLeft))
		{
			PrecisePermissiveFOV.addSteepBump(activeViews.get(viewIndex), bottomRight);
			PrecisePermissiveFOV.checkView(activeViews, viewIndex);
		}
		/**
		 * The current square is completely between the two lines of the current view, so we split
		 * the current view into two views. One above and one below the current square.
		 */
		else
		{
			int shallowViewIndex = viewIndex;
			viewIndex++;
			int steepViewIndex = viewIndex;

			activeViews.add(shallowViewIndex, activeViews.get(shallowViewIndex).clone());

			PrecisePermissiveFOV.addSteepBump(activeViews.get(shallowViewIndex), bottomRight);
			if (!PrecisePermissiveFOV.checkView(activeViews, shallowViewIndex))
			{
				viewIndex--;
				steepViewIndex--;
			}

			PrecisePermissiveFOV.addShallowBump(activeViews.get(steepViewIndex), topLeft);
			PrecisePermissiveFOV.checkView(activeViews, steepViewIndex);
		}
	}
}
